package com.acyouzi.leetcode.array;

/**
 * 17/9/18 12:36
 *
 * @author sunxu
 */
public class Matrix {
  public int[][] updateMatrix(int[][] matrix) {
    int row = matrix.length;
    if (row == 0) return matrix;
    int col = matrix[0].length;
    int[][] dp = new int[row][col];
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        dp[i][j] = Integer.MAX_VALUE-1;
      }
    }
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (matrix[i][j] == 0){
          dp[i][j] = 0;
        }else{
          if (i > 0) dp[i][j] = Math.min(dp[i][j],dp[i-1][j]+1);
          if (j > 0) dp[i][j] = Math.min(dp[i][j],dp[i][j-1]+1);
        }
      }
    }
    for (int i = row-1; i >= 0 ; i--) {
      for (int j = col-1; j >= 0 ; j--) {
        if (i < row-1) dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1);
        if (j < col-1) dp[i][j] = Math.min(dp[i][j],dp[i][j+1]+1);
      }
    }
    return dp;
  }
}
